package medium;

import com.sun.istack.internal.NotNull;

/**
 * 中等难度
 * 给予两个非负整数，用链表倒序保存每个整数。比如，357保存为链表 7 -> 5 -> 3
 * 求和两个整数，以链表结构返回
 * <p>
 * 假定这两个非负整数不包含任何前导0，比如023
 * <p>
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 * <p>
 * 思考几种情况：
 * 1. 两个整数的长度不一致
 * 2. 整数进位
 * 3. 最高位整数进位
 *
 * @author zj
 * @date 2018/07/31
 * @see <a href="https://leetcode.com/problems/add-two-numbers/description/">题目</a>
 * @see <a href="https://leetcode.com/articles/add-two-numbers/">解答</a>
 */
public class AddTwoNumbers {

    /**
     * 首先计算两个链表长度，定义两个链表引用longList和shortList，分别指向长度大的链表和长度小的链表
     * 先计算两个链表同时存在的位，和大于10进1位
     * 然后再计算长链表是否需要进位，尤其是高位是否需要进位，如果需要，要创建一个新的结点
     * <p>
     * 时间复杂度：O(max(m,n)) - m和n分别表示两个链表的长度(假定m>=n)。获取长度需要m或n次遍历，代码中有两个while循环，分别需要n次和(m-n)次遍历
     * 空间复杂度：O(1) - 函数中声明的链表引用了形参定义的链表
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = getLength(l1);
        int len2 = getLength(l2);
        ListNode longList = len1 >= len2 ? l1 : l2;
        ListNode shortList = len1 >= len2 ? l2 : l1;
        boolean carry = false;
        ListNode pre = null;
        while (shortList != null) {
            int temp = longList.val + shortList.val;
            temp = carry ? temp + 1 : temp;
            carry = temp >= 10;
            longList.val = carry ? temp - 10 : temp;
            pre = longList;
            longList = longList.next;
            shortList = shortList.next;
        }
        while (longList != null) {
            int temp = carry ? longList.val + 1 : longList.val;
            carry = temp >= 10;
            longList.val = carry ? temp - 10 : temp;
            if (!carry) {
                break;
            }
            pre = longList;
            longList = longList.next;
        }
        if (carry) {
            pre.next = new ListNode(1);
        }
        return len1 >= len2 ? l1 : l2;
    }

    /**
     * 文章的解答和自己的解答大同小异
     * 区别一：需要新建结果链表
     * <p>
     * 时间复杂度：O(max(m,n))
     * 空间复杂度：O(max(m,n))
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) {
                p = p.next;
            }
            if (q != null) {
                q = q.next;
            }
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }

    /**
     * 计算链表长度
     */
    private int getLength(@NotNull ListNode ln) {
        int length = 0;
        while (ln != null) {
            length++;
            ln = ln.next;
        }
        return length;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}